package solution.liuyu2783.offer;

/**
 * 剑指 Offer 04. 二维数组中的查找
 */
public class Q04_FindInArr_M {

	/**
     * 给定一个二维数组，其每一行从左到右递增排序，从上到下也是递增排序。给定一个数，判断这个数是否在该二维数组中。
     * Consider the following matrix:
     * [
     *   [1,   4,  7, 11, 15],
     *   [2,   5,  8, 12, 19],
     *   [3,   6,  9, 16, 22],
     *   [10, 13, 14, 17, 24],
     *   [18, 21, 23, 26, 30]
     * ]
     *
     * Given target = 5, return true.
     * Given target = 20, return false.
     *
     * 思路：该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。
     */
    public static void main(String[] args) {
        int [][] arr = new int[5][5];
        int[] a1 = new int[]{1,   4,  7, 11, 15};
        int[] a2 = new int[]{2,   5,  8, 12, 19};
        int[] a3 = new int[]{3,   6,  9, 16, 22};
        int[] a4 = new int[]{10, 13, 14, 17, 24};
        int[] a5 = new int[]{18, 21, 23, 26, 30};
        arr[0] = a1;
        arr[1] = a2;
        arr[2] = a3;
        arr[3] = a4;
        arr[4] = a5;

        int target = 18;

        int row = arr.length;
        int col = arr[0].length;
        int start_row = 0;
        int start_col = col -1;

        while (start_row <= row -1 && start_col >= 0){
            int num = arr[start_row][start_col];
            System.out.println("当前值："+ num);
            if(num > target){
                start_col --;
            }
            else if(num < target){
                start_row ++;
            }else {
                System.out.println("------找到重复值");
                return;
            }
        }
        System.out.println("++++ 没有找到");
    }
}
